package com.leetcode.binarytree;

import com.leetcode.datastructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2019/10/27
 * @description: 257. 二叉树的所有路径
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 * 说明: 叶子节点是指没有子节点的节点。
 * 输入:
 * <p>
 * 1
 * /   \
 * 2     3
 * \
 * 5
 * <p>
 * 输出: ["1->2->5", "1->3"]
 * todo:感觉二叉树没啥思路啊啊啊啊啊啊啊啊
 */
public class BinaryTreePaths257A {

	/**
	 * 当一个节点有几个子节点产生几个字符串	XXXX 思路错误！！！
	 * 修正：只有当一个节点不存在子节点的时候才进行返回！
	 *
	 * @param root
	 * @return
	 */
	public List<String> binaryTreePaths(TreeNode root) {
		List<String> result = new ArrayList<>();
		if (root == null) {
			return result;
		}
		// + "->";这个操作放在添加新节点的时候放在前面
		String path = root.val + "";
		if (root.left==null&&root.right==null){
			result.add(path);
		}
		if (root.left != null) {
			getPathII(root.left, result, path);
		}
		if (root.right != null) {
			getPathII(root.right, result, path);
		}
		return result;
	}

	/**
	 * version 1 fail!
	 *
	 * @param root
	 * @param list
	 * @param path
	 */
	private void getPaths(TreeNode root, List<String> list, String path) {
		///说明是叶子节点
		if (root == null) {
			list.add(path);
			return;
		}
		path += "->" + root.val;
		getPaths(root.left, list, path);
		getPaths(root.right, list, path);
//		if (root.left!=null){
//			getPaths(root.left,list,path);
//		}
//		if (root.right!=null){
//			getPaths(root.right,list,path);
//		}
	}

	private void getPathII(TreeNode root, List<String> list, String path) {
		path += "->" + root.val;
		///1.属于叶子节点
		if (root.left==null&&root.right==null){
			list.add(path);
			return;
		}
		///需要判断
		if (root.left!=null){
			getPathII(root.left,list,path);
		}
		if (root.right!=null){
			getPathII(root.right,list,path);
		}
	}

	/**
	 * 测试二叉树路径
	 */
	@Test
	public void testBinaryPaths() {
		TreeNode node = TreeNode.stringToTreeNode("[1,2,3,null,5]");
		System.out.println(binaryTreePaths(node));
	}

}
